package g

import (
	"math"
	"sort"
)

/*
 * @lc app=leetcode.cn id=16 lang=golang
 *
 * [16] 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。
请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
*/

// @lc code=start
func threeSumClosest(nums []int, target int) int {
	// return threeSumClosest1(nums, target) //304ms
	return threeSumClosest2(nums, target) //8ms
}

// 三层循环
func threeSumClosest1(nums []int, target int) int {
	minSum := math.MaxInt32
	minDelta := math.MaxInt32
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				delta := abs(target - (nums[i] + nums[j] + nums[k]))
				if minDelta > delta {
					minSum = nums[i] + nums[j] + nums[k]
					minDelta = delta
				}
			}
		}
	}
	return minSum
}

// 优化第三层循环，先排序，使第二层与第三层不碰头，o(n^2)
func threeSumClosest2(nums []int, target int) int {
	sort.Ints(nums)
	minSum := math.MaxInt32
	minDelta := math.MaxInt32
	for i := 0; i < len(nums); i++ {
		k := len(nums) - 1
		for j := i + 1; j <= k; j++ {
			for ; k > j; k-- {
				delta := abs(target - (nums[i] + nums[j] + nums[k]))
				if delta < minDelta {
					minSum = nums[i] + nums[j] + nums[k]
					minDelta = delta
				}
				if (nums[i] + nums[j] + nums[k]) <= target {
					break
				}
			}
		}
	}
	return minSum
}

func abs(val int) int {
	if val < 0 {
		return -val
	}
	return val
}

// @lc code=end
